This invention relates to vector quantization and, more particularly, to methods for forming a representation of a population from a look-up table having a predetermined number of attributes representing a larger number of attributes of the defined population. This invention is the result of a contract with the Department of Energy (Contract No. W-7405-ENG-36).
The field of vector quantization generally concerns the representation of a large number of specified attributes of a given population with a smaller number of attributes which are distributed over the population to approximate the distribution of the large number of attributes. In the following discussion, the population is pixels of a video display system and the attributes are colors to be associated with the pixels. It will be understood that the processes described herein are applicable to any population which can be described by specified attributes such that the term pixel means any specified population and the term color means any selected set of attributes.
A display system for a video system, e.g. a data processing system, displays discrete colors at individual pixels. The color represented at each pixel is typically formed from a plurality of phosphors, each generating a specific color amplitude response to an activating electron beam. A typical set of phosphors may represent the primary colors red, blue, and green, from which a complete color spectrum may be formed. High resolution digital representations of color images present twenty-four bit words, eight bits each for the three colors, to encode the color to be presented. This representation provides over 16 million discrete colors (2.sup.24).
A twenty-four bit color representation, however, is beyond the capability of most display systems, particularily where a real-time video capability is desired. A conventional display system uses only an eight bit word for color representation, which enables 256 colors (2.sup.8) to be selected to represent an image. The eight bit word does not, however, directly represent a color, but an address in a look-up table (LUT). The LUT then contains twenty-four bit representations at each of the 256 addresses. The display system assigns each actual color to one of the stored colors in the LUT and the stored color is actually used to generate the color displayed for each pixel during the raster generation of a color display. U.S. Pat. No. 4,751,446, issued Jun. 14, 1988, to Pineda et al., incorporated herein by reference, describes one embodiment of a LUT for providing color data to a video display.
To present a high resolution color image, an optimum set of colors must be selected to represent the image. A method that will compress a color image for LUT decompression will have the following features:
1. It must produce from a list of colors in the original image a second smaller list of colors (the representative LUT colors); the representative colors need not be present in the original image.
2. It must replace each of the original colors with an index into the LUT.
In one approach to color image quantization, a fixed set of color representations are stored in the LUT. The fixed set of colors may be uniformly spaced or may be based on a statistical distribution of the input colors. A uniform quantization is computationally fast, but provides poor color representations. In a statistical distribution representation, an algorithm must be selected to map the image colors onto the LUT to adequately represent the distribution of actual image colors.
A number of algorithms have been applied for this color mapping, some of which are discussed in P. Heckbert, "Color Image Quantization for Frame Buffer Display," 16 Computer Graphics, No. 3, pp. 297-302 (July 1982), incorporated herein by reference. In one algorithm, the densest regions in the image color distribution are selected to form the LUT. This algorithm apparently does not perform well on images with a wide variety of colors or with a small number of colors. Other algorithms attempt to define volumes in the color space, i.e., Voronoi regions, and select colors from those volumes, either as volume averages or as centroids of the volumes. Substantial computing time is required to define and iterate the Voronoi volumes.
Once a LUT is formed to represent the image colors, the image colors must then be mapped onto the LUT, i.e., each image color pixel must be replaced with the address of the representative color value in the LUT. This operation is a "nearest neighbor" problem. A straightforward approach is to test all LUT values for each image color and choose the closest LUT value. This approach requires substantial computation time.
Heckbert teaches a process for a locally sorted search. Color space is divided into equal volumes each containing a sorted list of LUT values. The list includes all LUT values that are the nearest neighbors of some point in that volume. Then any image color in the volume needs to be compared only with the LUT values in the sorted list.
However Heckbert provides only uniform volume sizes that may contain none, or a large number, of LUT values to be searched against image pixel values. Further, the list of values associated with each volume is not minimized.
Yet another search technique is described in J. H. Friedman et al., "An Algorithm for Finding Best Matches in Logarithmic Expected Time," 3 ACM Trans. Math. Software, pp. 209-226 (September 1977). A file (LUT) containing N records, each described by K real valued keys (color values) is searched for the closest match or nearest neighbor to a given query record (image color). The K-D tree structure described by Friedman does not adequately sort the data when forming the tree and additional sorting must be done when accessing the record space with a given key. Further, the K-D structure may not reach a terminal value on a single traverse of the tree and several traverses of the tree may be required, with a concomitant large storage space overhead required to maintain priority queues during the search.
These and other problems of the prior art are addressed by the present invention wherein an image reconstruction process sorts LUT values to a tree structure that allows a rapid traverse and a minimum nearest neighbor query at each terminal.
Accordingly, one object of the present invention is to generate a high resolution color representation of an image by rapidly replacing image pixel values with the addresses of assigned color values in a LUT.
It is another object of the present invention to provide a method for quantizing image colors from a LUT which operates on rapid sequential displays in real time.
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.